package main

import "fmt"

/*
寻找最长不含有重复字符的子串
*/
func main() {
	/*set := make([]uint8, 1, 10)
	fmt.Println(len(set), cap(set))
	set[0] = 10
	set[1] = 20
	fmt.Println(set)
	s := "abcabcbb"
	chs := []rune(s)
	fmt.Println(chs)
	fmt.Println(string(chs))*/
	//s := "abcabcbb"
	//s := "bbbbbbbb"

	fmt.Println(lengthOfLongestSubstring2("上海自来水来自海上"))
}

func lengthOfLongestSubstring1() {
	s := "pwwkew"
	chs := []rune(s)
	//maxLen := 0
	maxLenSubStr := ""
	for i := 0; i < len(chs); i++ {
		var set []rune
		for j := i; j < len(chs); j++ {
			k := 0
			for ; k < len(set); k++ {
				if set[k] == chs[j] {
					break
				}
			}
			if k == len(set) {
				set = append(set, chs[j])
			} else {
				break
			}
		}
		if len(maxLenSubStr) < len(set) {
			maxLenSubStr = string(set)
		}
	}

	fmt.Printf("最长不含有重复字符的子串为：%s", maxLenSubStr)
}

// 我自己的题解
func lengthOfLongestSubstring2(s string) int {
	lastOccurred := make(map[rune]int)
	maxLen, start := 0, 0

	for i, ch := range []rune(s) {
		if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
			start = lastI + 1
		} else if i-start+1 > maxLen {
			maxLen = i - start + 1
		}
		lastOccurred[ch] = i
	}

	return maxLen
}

// leetcode用时最短的题解
func lengthOfLongestSubstring3(s string) int {
	location := [255]int{}
	for i := range location {
		location[i] = -1
	}
	maxLen, left := 0, 0

	for i, v := range s {
		if location[v] >= left {
			left = location[v] + 1
		} else if i-left+1 > maxLen {
			maxLen = i - left + 1
		}
		location[v] = i
	}

	return maxLen
}
